package q45_jump;

public class Solution_1 {
    public static void main(String[] args) {
        Solution_1 s = new Solution_1();
        int[] nums = {1,1,2,2,0,1,1};
        // int[] nums = {2,3,0,1,4};
        int a = s.jump(nums);
        System.out.println(a);
    }

    public int jump(int[] nums) {
        if (nums.length == 1) {
            return 0;
        }
        if (nums[0] >= nums.length - 1) {
            return 1;
        }
        int count = 2;
        int[] res = MaxLengths(0,nums);

        for (; res[1] < nums.length - 1; count++) {
            res = MaxLengths(res[0],nums);
        }
        return count;
//        int[] res = MaxLengths(0,nums);
//        while (res[1] < nums.length - 1) {
//            res = MaxLengths(res[0],nums);
//            count++;
//        }
//
//        return count;
    }

    public int[] MaxLengths(int index, int[] nums) {
        int max = 0;
        int[] res = new int[2];
        for (int i = 0; (i <= nums[index]) && (index + i) < nums.length; i++) {
            int bin = index + i  + nums[index + i];

            if (bin >= nums.length){
                return new int[] {i, bin};
            }

            if (bin >= max){
                res[0] = index + i;
                res[1] = bin;
                max = bin;
            }

        }

        return res;
    }
}
